A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
This invention relates to computer networks. More particularly, the invention relates to methods and systems for determining a routing topology of a computer network by obtaining and utilizing Interior Gateway Protocol (IGP) routing information or Exterior Gateway Protocol (EGP) routing information.
Computer networks are growing in complexity and criticality. For example, a large corporation may support a computer network with tens of thousands of individual computers and thousands of network routers, hubs, repeaters or other network connectivity hardware. These networks are in many cases vital to an organization""s functioning, and in some cases are mission- or life-critical.
Because of increasing network size and complexity, service provider networks (such as Internet service providers or application service providers) in particular are quickly growing beyond the ability of current methods to manage them. For example, the typical level of modification and reconfiguration in a complex service provider network is at best difficult and time-consuming to understand or document.
Although several commercially and freely available software packages attempt to address network complexity problems, and some theoretical work has been done in this field, effective solutions to comprehensive network management problems in complex networks remain elusive or non-existent.
Increasingly, the problem in a large, complex network is not a change in the actual physical topology. There are known methods for solving the problem of single points of failure and link layer failures. For example, protection switching on the SONET layer of a network, as known to one skilled in the art, can address physical topology management issues such as single points of failure or link layer failures among other things. The automatic protection switching (APS) feature is supported, for example, on Cisco 7500 series routers and Cisco 12000 series routers, which allow switchover of packet-over-SONET (POS) circuits in the event of circuit failure, and is often required when connecting SONET equipment to Telco equipment. Here, APS refers to the mechanism of using a xe2x80x9cprotectxe2x80x9d POS interface in the SONET network as the backup for a xe2x80x9cworkingxe2x80x9d POS interface. When the working interface fails, the protect interface quickly assumes its traffic load.
The problem in many service provider networks is the topology change produced by the routing protocols. Routing protocols and routing policies are how service providers control traffic and manage traffic across their network and with other service provider networks. For example, a large service provider network may have a relatively stable configuration of computing nodes and interconnection hardware, which can dynamically load balance a variety of incoming network traffic primarily through packet traffic rerouting. Thus, when one node on the service provider network is overwhelmed by traffic, software methods can be used to reconfigure routers and compute nodes so that incoming traffic is redistributed and congestion is decreased or eliminated.
The existing efforts in this area are concerned with discovering physical networks and physical topologies, not routing topologies. However, physical topologies alone do not necessarily provide a complete and accurate representation of the topology of information flow in a network or networks, which is affected not only by the topology but also by routing considerations. For example, even though a router may be directly connected to a particular network or networks, traffic bound for that network or those networks may never cross that router. The actual flow of packets through the network or networks is controlled by the routing protocols via techniques known to those skilled in the art of network management, such as, for example, route summarization (where an internetwork is divided into logical areas, with each area""s border router advertising only a single summary route to other areas in order to reduce routing table size), route filters (where an additional metric rates relative reliability of individual networks as a source from which to determine optimal routes), and related routing polices.
As a further example, physical topology alone does not take into account information flow within a network as affected by multiple routers being directly connected to a particular network. How the traffic bound for that network is distributed, if at all, across those routers is a result of specific settings in the routing protocols. Thus, by changing settings in the routing protocols, traffic distribution, and thus routing topology, is fundamentally altered.
In terms of the ISO/OSI network model, (described in Douglas Comer""s two volume work entitled xe2x80x9cInternetworking with TCP/IP,xe2x80x9d which is hereby incorporated by reference), previous work is focussed on understanding layer 2 and layer 3 topologies. The previous work does not analyze or take into account actual traffic flow.
While several commercial products for determining network topology are available, these products have serious drawbacks relating to their inability to take into account routing topology. For example, HP""s Openview does not consider subnet masks. Other commercial products such as Riversoft""s Openriver do not take into account routing protocols at all.
As recognized by the inventors, IGP information, such as may be obtained by IGP link state databases, may be particularly useful in determining routing topologies. However, the existing methods do not utilize IGP information in routing topology determination. Thus, there is a need in the art for a method of determining routing topology of a computer network, particularly in the context of complex networks, and for obtaining IGP information useful in determining routing topology of a computer network.
It is an object of the present invention to solve the problems described above associated with existing methods of determining network topologies.
It is still another object of the invention to provide a method for determining routing topologies in networks, including complex networks.
It is still another object of the invention to provide a method for determining routing topologies in networks, including complex networks, that takes into account actual packet routing traffic flows and routing topologies.
In one embodiment, the invention provides a method and system for determining routing topology in a computer network, and comprises obtaining IGP information, obtaining EGP information, and utilizing the IGP and EGP information to determine network topologies.
In another embodiment, the invention provides a method and system for determining routing topology in a computer network, and comprises obtaining IGP information to determine the effects of routing protocols on network topology; obtaining EGP information by obtaining Border Gateway Protocol (BGP) information utilizing an EGP peer; and utilizing the IGP and EGP information to create topological network views.
In still another embodiment, the invention provides a method and system for obtaining IGP information by querying IGP link state databases.
In still another embodiment, the invention comprises a method for obtaining IGP network information useful in determining network routing topologies, comprising querying a router for its router identifier and all its area identifiers, counting the router""s number of area identifiers to determine whether the router is an ABR or an ASBR, querying the router""s link state database for the lowest area identifier on the router, importing all the Type 1 and Type 2 LSAs for that area into the database of the network discovery software engine, importing from the router""s link state database only those networks outside the router""s autonomous system that are also directly connected to an ASBR, then moving to the next highest area identifier in the router""s database to repeat importing Type 1 and Type 2 LSAs for that area into the database of the network discovery software engine and importing from the router""s link state database only those networks outside the router""s autonomous system that are also directly connected to an ASBR repeating this process until there are no more areas on the router that have not been processed, then starting with the lowest area identifier discovered, sweeping all networks in the area making LSAs other than Type 1 or Type 2, and repeating the entire process for every router discovered.
In still another embodiment, a method in accordance with the invention comprises obtaining EGP information, useful in determining network routing topologies, by obtaining BGP information utilizing an EGP peer, by using a software based routing engine on a host that the network discovery software is installed on, configuring the routing software to enable the specific EGP and to announce only the host route to the software-based router, establishing a peer relationship with an EGP speaking router in the network, loading the EGP database from the EGP router, and importing the EGP database into the network discovery software for processing.
In still another embodiment, a method in accordance with the invention comprises obtaining and utilizing the IGP and EGP information, useful in creating topological network views, by instantiating the routing protocol created topology using routing and software methods described in U.S. Pat. No. 6,108,702 titled xe2x80x9cMethod and Apparatus for Determining Accurate Topology Features of a Network,xe2x80x9d issued Aug. 22, 2000 and incorporated herein by reference in its entirety, drawing a map of the network starting with IGP areas and allowing the user to select the BGP topology or the EGP topology including confederations, communities, and route reflectors.
In still another embodiment, the invention provides a method and system for determining routing topology in a computer network, and comprises obtaining IGP information to determine the effects of routing protocols on network topology using techniques described herein; obtaining EGP information by obtaining BGP information utilizing an EGP peer by using a software based routing engine on a host that the network discovery software is installed on, configuring the routing software to enable specific the EGP and to announce only the host route to the software-based router, establishing a peer relationship with an EGP speaking router in the network, loading the EGP database from the EGP router, and importing the EGP database into the network discovery software for processing; and utilizing the IGP and EGP information to create topological network views by instantiating the routing protocol created topology using routing and software methods described, for example, in the above referenced U.S. Pat. No. 6,108,702. The method further involves drawing a map of the network starting with IGP areas and allowing the user to select the BGP topology or the EGP topology including confederations, communities, and route reflectors.